|
In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph)〔.〕 is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph. Distance-hereditary graphs were named and first studied by , although an equivalent class of graphs was already shown to be perfect in 1970 by Olaru and Sachs.〔Olaru and Sachs showed the α-perfection of the graphs in which every cycle of length five or more has a pair of crossing diagonals (, Theorem 5). By , α-perfection is an equivalent form of definition of perfect graphs.〕 It has been known for some time that the distance-hereditary graphs constitute an intersection class of graphs, but no intersection model was known until one was given by . ==Definition and characterization== The original definition of a distance-hereditary graph is a graph ''G'' such that, if any two vertices ''u'' and ''v'' belong to a connected induced subgraph ''H'' of ''G'', then some shortest path connecting ''u'' and ''v'' in ''G'' must be a subgraph of ''H'', so that the distance between ''u'' and ''v'' in ''H'' is the same as the distance in ''G''. Distance-hereditary graphs can also be characterized in several other equivalent ways:〔; ; ; , Theorem 10.1.1, p. 147.〕 *They are the graphs in which every induced path is a shortest path, or equivalently the graphs in which every non-shortest path has at least one edge connecting two non-consecutive path vertices. *They are the graphs in which every cycle of length at least five has two or more diagonals, and in which every cycle of length exactly five has at least one pair of crossing diagonals. *They are the graphs in which every cycle of length five or more has at least one pair of crossing diagonals. *They are the graphs in which, for every four vertices ''u'', ''v'', ''w'', and ''x'', at least two of the three sums of distances ''d''(''u'',''v'')+''d''(''w'',''x''), ''d''(''u'',''w'')+''d''(''v'',''x''), and ''d''(''u'',''x'')+''d''(''v'',''w'') are equal to each other. *They are the graphs that do not have as isometric subgraphs any cycle of length five or more, or any of three other graphs: a 5-cycle with one chord, a 5-cycle with two non-crossing chords, and a 6-cycle with a chord connecting opposite vertices. *They are the graphs that can be built up from a single vertex by a sequence of the following three operations, as shown in the illustration: *#Add a new ''pendant vertex'' connected by a single edge to an existing vertex of the graph. *#Replace any vertex of the graph by a pair of vertices, each of which has the same set of neighbors as the replaced vertex. The new pair of vertices are called ''false twins'' of each other. *#Replace any vertex of the graph by a pair of vertices, each of which has as its neighbors the neighbors of the replaced vertex together with the other vertex of the pair. The new pair of vertices are called ''true twins'' of each other. *They are the graphs that can be completely decomposed into cliques and stars (complete bipartite graphs ''K''1,''q'') by a split decomposition. In this decomposition, one finds a partition of the graph into two subsets, such that the edges separating the two subsets form a complete bipartite subgraph, forms two smaller graphs by replacing each of the two sides of the partition by a single vertex, and recursively partitions these two subgraphs.〔. A closely related decomposition was used for graph drawing by and (for bipartite distance-hereditary graphs) by .〕 *They are the graphs that have rank-width one, where the rank-width of a graph is defined as the minimum, over all hierarchical partitions of the vertices of the graph, of the maximum rank among certain submatrices of the graph's adjacency matrix determined by the partition.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Distance-hereditary graph」の詳細全文を読む スポンサード リンク
|